This invention can relate to processing data blocks. More particularly, this invention can relate to correcting errors detected in data blocks by identifying likely error events.
Data transmitted in and between data processing systems can be corrupted by errors caused by noise, jitter, or other factors. In order to detect and possibly correct these errors, many systems introduce a level of redundancy to the data. For instance, redundancy can be introduced through the use of a checksum, where the logical bits of each block of data are added together to generate a modular sum that is transmitted with the data. Data blocks and checksums can be any suitable number of bits. For instance, a single-bit checksum can be computed by determining a logical XOR of the bits of the corresponding data block.
When the data block is received, the logical bits of each received data block can again be added together according to the checksum equation, and the resulting sum can be compared to the checksum received for that block. If an inconsistency exists between the computed sum and the received checksum, then it is likely that an error was introduced into the data block or the checksum during transmission or receipt. For example, in one common implementation, a parity encoder can attach a checksum of zero to each data block before transmitting it over a channel. In this case, the received checksum should always be zero. As another example, if a tensor-product parity code is used, the received checksum can be provided by a parity-hiding code instead of a standard parity encoder. An indication of whether or not a received data block is consistent with its received checksum can be recorded as a “correction flag” that takes a certain value if no error is detected and another value if at least one error is detected.
In some systems, circuitry receiving the data can not only detect possible errors in the data blocks, but can also determine which logical bits in the data blocks were likely to be changed. Information about which bits may be corrupted can be represented by a multi-bit mask or “pattern.” In addition, some systems can determine how likely it is that a certain pattern correctly identifies which bits have been corrupted. Information about this likelihood can be recorded as an “error-event metric.” A pattern and its corresponding error event metric can together constitute an “error event.”
Given a set of received data blocks, its correction flags, and its error event information, it is possible to identify the most likely set of error events that will correct the identified data errors. However, performing an exhaustive search through the possible combinations of error events can be very computationally intensive due to the relatively large number of possible combinations of error events across a relatively large number of data blocks.
In view of the foregoing, it would be desirable to provide methods and apparatus that can efficiently identify the most likely set of error events that will correct errors that have been identified in data blocks.